Huffman-Kodierung

Huffman-Kodierung,

 

ein nach dem amerikanischen Mathematiker David Huffman (1925-1999) benanntes Verfahren zur Komprimierung von Daten. Die Huffman-Kodierung ordnet jedem Zeichen oder Symbol nach der Wahrscheinlichkeit seines Auftretens eine Bitfolge zu, wobei häufig auftretende Zeichen durch kurze Sequenzen repräsentiert werden und seltene Zeichen dafür durch längere. Dadurch wird eine kürzestmögliche Codelänge erzielt. Aus diesem Grund findet die Huffman-Kodierung in vielen Komprimierungsprogrammen und Dateiformaten Verwendung, etwa bei JPEG. Mit der Huffmann-Kodierung können beliebige Daten komprimiert werden, z. B. Texte, Grafiken, Dokumente im World Wide Web (WWW), und es werden - im Gegensatz zu manchen anderen Verfahren - stets nennenswerte Komprimierungsraten erzielt, da praktisch immer manche Datenelemente häufiger benutzt werden als andere. Ein Beispiel, welches das Prinzip der Huffman-Kodierung verdeutlicht, ist das Morsealphabet. Dem im Deutschen am häufigsten verwendeten Buchstaben »e« ist das kürzeste Morsezeichen »·« zugeordnet, dem seltenen Buchstaben »q« das lange Morsezeichen »--·-«.

 

Die Übersetzung eines vorhandenen Zeichenalphabets in nach Auftretenswahrscheinlichkeiten abgestufte Bitfolgen kann oft durch Probieren vorgenommen werden. Huffman erfand aber 1952 ein Verfahren, das tatsächlich minimale Codelängen garantiert. Zwischen zwei Codezeichen muss nicht einmal ein »Komma« gesetzt werden, um die Zeichen voneinander zu trennen, d. h., das Ende einer Bitfolge kann ohne zusätzliche Information erkannt werden. Huffmans Algorithmus arbeitet rekursiv: Alle Symbole werden zunächst nach ihrer Häufigkeit in einer Reihe angeordnet. Den beiden seltensten Symbolen wird dann als letzte Codeziffer eine »0« und eine »1« zugeordnet, sie werden anschließend zu einem neuen Zeichen mit der Summe ihrer Wahrscheinlichkeiten zusammengefasst. Dieses neue Zeichen wird nun anstelle der beiden alten Zeichen in die ursprüngliche Reihe eingeordnet (sie hat damit ein Element weniger) und das Verfahren wird für die neue Reihe wiederholt usw., bis die Reihe nur noch zwei Elemente enthält, denen eine »0« und eine »1« zugewiesen werden (die Zusammensetzung von zwei Zeichen stellt einen Knoten dar; die durch die Rekursion entstehende Struktur lässt sich als binärer Baum auffassen). Die Bitfolge eines jeden ursprünglichen Zeichens ergibt sich nun - von rechts nach links gelesen - als Folge der Nullen und Einsen, die dem Zeichen selbst, dann den zugehörigen Zusammensetzungen zu neuen Zeichen zugeordnet wurden (in der Betrachtungsweise des Baums die Folge von Nullen und Einsen eines Pfads).

 

Meist wird die Huffman-Kodierung nach einer festen Wahrscheinlichkeitstabelle für die Auftretenswahrscheinlichkeit der einzelnen Zeichen vorgenommen (statische Variante). Alternativ können die zu kodierenden Daten vor der Kodierung statistisch untersucht und die Häufigkeit der einzelnen Zeichen berechnet werden (dynamische Variante). Da diese Vorgehensweise die Eigenheiten der vorliegenden Daten berücksichtigt, können höhere Komprimierungsraten erzielt werden, dafür entsteht ein vergrößerter Rechenaufwand. Adaptive Varianten verwenden eine Mischung aus statisch und dynamisch bestimmten Wahrscheinlichkeiten. Nur ein Teil der Auftretenshäufigkeiten wird neu ermittelt.